
"""
105. 从前序与中序遍历序列构造二叉树
"""
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.dict = {}

    """
     * 分解二叉树
     * 定义build函数，构建二叉树，先构建根节点，在构建左右节点
     * 特点：前序遍历数组，第一个节点是根节点，依次是左节点，右节点，中序遍历，根节点左边是左子树，右边是右子树
    """
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        for i in range(len(inorder)):
            self.dict[inorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1, inorder, 0, len(inorder) - 1)

    '''遍历二叉树'''
    def build(self, preorder: List[int], pre_start, pre_end, inorder: List[int], in_start, in_end) -> Optional[TreeNode]:
        if pre_start > pre_end:
            return None
        root = TreeNode(preorder[pre_start])
        in_root_index = self.dict.get(preorder[pre_start])
        left_size = in_root_index - in_start

        # 前序位置
        root.left = self.build(preorder, pre_start + 1, pre_start + left_size, inorder, in_start, in_root_index - 1)
        # 中序位置
        root.right = self.build(preorder, pre_start + left_size + 1, pre_end, inorder, in_root_index + 1, in_end)
        # 后序位置
        return root